#ifndef HEAP_H
#define HEAP_H
#include <iostream>

namespace tkg{

template<typename T,int HEAP_SIZE=512>
class Heap{
public:
    Heap(){
        m_t = new T*[HEAP_SIZE];
        for(int i = 0; i < HEAP_SIZE; ++i)
            m_t[i] = 0;
        m_size = 0;
    }

    ~Heap(){
        for(int i = 0; i < m_size; ++i){
            delete m_t[i];
        }
        delete [] m_t;
    }

    inline void pify(const int &i){
        if(i < 0){
            return;
        }
        int min;
        int l = 2*i + 1;
        int r = 2*i + 2;
        if(l < m_size && *m_t[l] < *m_t[i])//重载friend inline bool operator<(const T &a, const T &b )
            min = l;
        else
            min = i;
        if(r < m_size && *m_t[r] < *m_t[min])
            min = r;
        if(min != i){
            T * temp = m_t[min];
            m_t[min] = m_t[i];
            m_t[i] = temp;
            pify(min);
        }
    }

    inline void test(){
        for(int i = 0; i < m_size; ++i){
            std::cout << *m_t[i] << " ";//重载friend inline ostream & operator <<(ostream & os,const T &t);
        }
        std::cout << std::endl;
    }


     inline void insert(const T & temp){
        if(m_size >= HEAP_SIZE)
            return;
        T * t = new T(temp);
        m_t[m_size++] = t;
        for(int i = m_size/2 -1; i >= 0; --i)
            pify(i);
    }


    inline int size(){ return m_size; }

    inline void pop(){ del(0); }

    inline T & top(){ return *m_t[0]; }

    inline void remove(const T & temp){
        for(int i = 0; i < m_size; ++i){
            if(*m_t[i] == temp){//重载friend inline bool operator==(const T &a,const T &b)
                del(i);
                return;
            }
        }
    }

    inline bool contains(const T &temp){
        for(int i = 0; i < m_size; ++i){
            if(*m_t[i] == temp)
                return true;
        }
        return false;
    }

    inline void update(const T & temp,const T & n_temp){
        for(int i = 0; i < m_size; ++i){
            if(*m_t[i] == temp){//重载friend inline bool operator==(const T &a,const T &b)
                *m_t[i] = n_temp;
                pify(i);
                return;
            }
        }
    }

private:
     void del(const int &i){
        --m_size;
        if( m_size >= 0){
            delete m_t[i];
            m_t[i] = m_t[m_size];
            m_t[m_size] = 0;
            if(m_size > 0)
                pify(i);
        }
    }
    int m_size;
    T ** m_t;
};
}

#endif // HEAP_H
